/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package tri;

import java.util.ArrayList;
import java.util.List;
import util.Util;

/**
 *
 * @author Xuan Huy
 */
public final class Tas {

    /**
     * La structure de données représentant le tas max ou min.
     */
    protected List<Integer> tas;

    /**
     * Le constructeur sans argument par défaut construit un tas vide.
     */
    public Tas() {
    }

    /**
     * Le constructeur construit le tas à partir la
     * <code>liste</code> (ordonnée ou non) passée en paramètres.
     *
     * @param liste une liste d'entiers.
     */
    public Tas(List<Integer> liste) {
        construireTasMax(liste);
    }

    /**
     * La méthode retourne l'indice du noeud gauche du noeud d'indice
     * <code>i</code>.
     *
     * @param i indice du noeud dont on veut trouver l'indice du noeud gauche.
     * @return indice du noeud gauche du noeud d'indice <code>i</code>.
     */
    protected int gauche(int i) {
        return 2 * i + 1;
    }

    /**
     * La méthode retourne l'indice du noeud droite du noeud d'indice
     * <code>i</code>.
     *
     * @param i indice du noeud dont on veut trouver l'indice du noeud droite.
     * @return indice du noeud droite du noeud d'indice <code>i</code>.
     */
    protected int droite(int i) {
        return 2 * i + 2;
    }

    /**
     * La méthode retourne l'indice du noeud parent du noeud d'indice
     * <code>i</code>.
     *
     * @param i indice du noeud dont on veut trouver l'indice du noeud parent.
     * @return indice du noeud parent du noeud d'indice <code>i</code>.
     */
    protected int parent(int i) {
        return (i - 1) / 2;
    }

    /**
     * La méthode construite le tas à partir la
     * <code>liste</code> (ordonnée ou non) passée en paramètres.
     *
     * @param liste une liste d'entiers.
     */
    protected void construireTasMax(List<Integer> liste) {
        tas = new ArrayList<>(liste);
        int k = liste.size() / 2 - 1;
        for (int i = k; i >= 0; i--) {
            entasserTasMax(i);
        }
    }

    /**
     * La méthode assure que les contraintes d'un tas max n'est pas violée. Elle
     * rétablit ces contraintes si un noeud est strictement inférieur à un de
     * ses noeuds enfants.
     *
     * @param indice indice du noeud qui viole les contrainte d'un tas max.
     * @throws IndexOutOfBoundsException si <code>indice</code>
     * &lt; <code>0</code> et <code>indice</code> &gt;= <code>tas.size()</code>.
     */
    protected void entasserTasMax(int indice) throws IndexOutOfBoundsException {
        if (indice < 0 || indice >= tas.size()) {
            throw new IndexOutOfBoundsException();
        }
        int max = indice;
        int g = gauche(indice);
        int d = droite(indice);
        if (d < tas.size() && tas.get(d).compareTo(tas.get(max)) > 0) {
            max = d;
        }
        if (g < tas.size() && tas.get(g).compareTo(tas.get(max)) > 0) {
            max = g;
        }
        if (max != indice) {
            Util.echanger(tas, indice, max);
            entasserTasMax(max);
        }
    }

    /**
     * La méthode retourne une liste triée dans l'ordre croissant par la méthode
     * tri par tas.
     *
     * @return une liste d'entiers triée.
     */
    public List<Integer> triTas() {
        List<Integer> resultat = new ArrayList<>();
        for (int i = tas.size() - 1; i > 0; i--) {
            Util.echanger(tas, 0, i);
            Integer elementMax = tas.remove(i);
            resultat.add(0, elementMax);
            entasserTasMax(0);
        }
        resultat.add(0, tas.remove(0));
        return resultat;
    }

    /**
     * La méthode augmente la valeur du noeud d'indice
     * <code>indice</code> en la remplaçant par
     * <code>nouvelleCle</code>.
     *
     * @param indice indice du noeud dont on veut augmenter la valeur.
     * @param nouvelleCle la nouvelle valeur.
     * @throws IndexOutOfBoundsException voir
     * {@link tri.Tas#entasserTasMax(int)}.
     * @throws IllegalArgumentException si <code>nouvelleCle</code> est
     * inférieure à la valeur actuelle du noeud d'indice <code>indice</code>.
     */
    public void augmenterCleTasMax(int indice, int nouvelleCle)
            throws IndexOutOfBoundsException, IllegalArgumentException {
        if (indice < 0 || indice >= tas.size()) {
            throw new IndexOutOfBoundsException();
        }
        if (tas.get(indice).compareTo(nouvelleCle) > 0) {
            throw new IllegalArgumentException();
        }
        tas.set(indice, nouvelleCle);
        while (indice > 0
                && tas.get(indice).compareTo(tas.get(parent(indice))) > 0) {
            Util.echanger(tas, indice, parent(indice));
            indice = parent(indice);
        }
    }

    /**
     * La méthode insère un nouveau noeud dans le tas max, tout en respectant
     * les contraintes.
     *
     * @param cle la valeur du nouveau noeud.
     */
    public void insererTasMax(int cle) {
        tas.add(Integer.MIN_VALUE);
        augmenterCleTasMax(tas.size() - 1, cle);
    }

    /**
     * La méthode supprime le noeud d'indice
     * <code>indice</code> d'un tas max.
     *
     * @param indice indice du noeud supprimé.
     * @throws IndexOutOfBoundsException voir
     * {@link tri.Tas#entasserTasMax(int)}.
     */
    public void supprimerTasMax(int indice) throws IndexOutOfBoundsException {
        if (indice < 0 || indice >= tas.size()) {
            throw new IndexOutOfBoundsException();
        }
        tas.remove(indice);
        construireTasMax(tas);
    }

    /**
     * La méthode retourne le tas actuel.
     *
     * @return le tas actuel.
     */
    public List<Integer> getTas() {
        return tas;
    }

    /**
     * La méthode construit le nouveau tas à partir la
     * <code>liste</code> passée en paramètre.
     *
     * @param liste une liste d'entiers, triées ou non.
     */
    public void setTas(List<Integer> liste) {
        construireTasMax(liste);
    }
}
